package fingerprint;

/**
 * Created by Alison on 2016/11/10.
 */
public class QuickSelect {

    private static Comparable median3(Comparable[] data , int left, int right){
        int center = (left + right) /2 ;
        if(data[center].compareTo(data[left]) < 0)
            swapReferences(data, left, center);
        if(data[right].compareTo(data[left]) < 0)
            swapReferences(data, left, right);
        if(data[right].compareTo(data[center]) < 0)
            swapReferences(data, center, right);
        swapReferences(data, center, right -1);

        return data[right - 1];

    }

    private static void swapReferences(Comparable[] data, int src, int des){
        Comparable tmp;
        tmp = data[des];
        data[des] = data[src];
        data[src] = tmp;
    }

    private static void  quickSelect(Comparable[] data, int left, int right, int k){
        if(left + CUTOFF <= right){
            Comparable pivot = median3(data, left, right);

            int i = left;
            int j= right -1;
            for(; ;){
                while(data[++i].compareTo(pivot) < 0){}
                while(data[--j].compareTo(pivot) > 0) {}

                if(i < j)
                    swapReferences(data, i, j);
                else
                    break;
            }

            swapReferences(data, i, right - 1);

            if(k <= i){
                quickSelect(data,left, i - 1, k);
                //return data[left+k-1];
            }
            else{
                quickSelect(data, i + 1, right, k);
                //return data[left + k -1];

            }
        }
        else{
            insertionSort(data, left, right);
            //return data[left + k -1];
        }
    }

    private static void insertionSort(Comparable[] data, int left, int right){
        int j;
        for(int p = left + 1; p <= right; p++){
            Comparable tmp = data[p];
            for(j = p; j > left && tmp.compareTo(data[j-1]) < 0; j--)
                data[j] = data[j-1];
            data[j] = tmp;

        }
    }

    public static Comparable quickSelect(Comparable[] data, int k){

        quickSelect(data, 0, data.length - 1, k);
        return data[k -1];

    }


    public static void main(String[] args){
        Comparable[] a = new Comparable[20];
        for(int i = 0; i < a.length; i ++)
            a[i] = (int) (Math.random() * 100);
        for(int i = 0; i < a.length; i ++)
            System.out.print(a[i] + ", ");
        System.out.println("");
        Comparable b =  quickSelect(a, 8);
        for(int i = 0; i< a.length; i++)
            System.out.print(a[i] +", ");
        System.out.println("");
//        System.out.println(b);
    }

    private final static int CUTOFF = 10;

}